/*
1552. 两球之间的磁力
https://leetcode.cn/problems/magnetic-force-between-two-balls/description/?envType=problem-list-v2&envId=binary-search
难度：中等  李佳韵  2024/09/19
二分查找
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
private:
    // 检查是否能以给定的最小距离放置 m 个球
    bool check(vector<int>& position, int m, int mid) {
        int lastPos = position[0];
        int count = 1;
        for (int i = 1; i < position.size(); ++i) {
            if (position[i] - lastPos >= mid) {
                lastPos = position[i];
                count++;
                if (count == m)
                    return true;
            }
        }
        return false;
    }

public:
    // 计算在给定位置向量中放置 m 个球的最大距离
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        int left = 1;
        int right = position.back() - position.front();
        int net = 0;
        while (left <= right) {
            int mid = (right + left) / 2;
            if (check(position, m, mid)) {
                net = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return net;
    }
};

int main() {
    cout << "请输入位置向量的大小：";
    int n;
    cin >> n;
    vector<int> position(n);
    cout << "请输入位置向量的元素：";
    for (int i = 0; i < n; ++i) {
        cin >> position[i];
    }
    cout << "请输入要放置的球的数量：";
    int m;
    cin >> m;

    Solution solution;
    int result = solution.maxDistance(position, m);
    cout << "在给定位置向量中放置 " << m << " 个球的最大距离为：" << result << endl;

    return 0;
}